import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;


public class LinkList {
	private Node head;
	private Node tail;
	private int size;
	
	
	private static class Node{
		int data;
		Node next;
		
		private Node(int newdata){
			data = newdata;
			next = null;
		}
	
	}
	
	//Wrapper class for counting
	public class Counter{
		int value;
	}
	
	public LinkList(){
		head = null;
		tail = null;
		size = 0;
	}
	
	public Node addFirst(int data){
		Node temp = new Node(data);
		head = temp;
		tail = temp;
		size++;
		return temp;
	}
	
	public void add(int data){
		tail = add(tail, data);
	}
	
	public Node add(Node node, int data){
		//base situation
		if(node == null){
			return addFirst(data);
		}
		
		node = new Node(data);
		tail.next = node;
		tail = node;
		size++;
		return node;
		
	}
	
	public void remove(Node node, int data){
		if(node == null)
		{
			return;
		}
		Node current = node;
		Node previous = current;
		
		if(current.data == data){
			head = head.next;
			size--;
		}
		while(current != null){
			if(current.data == data){
				previous.next = current.next;
				size--;
				break;
			}
			previous = current;
			current = current.next;
		}
		
		
		
	}
	
	public int getSize(){
		return this.size;
	}
	
	
	public String toString(){
		Node node = head;
		String output = "";
		while(node != null){
			output = output + node.data + "-->";
			node = node.next;
		}
		
		return output + "Tail";
	}
	
	public Node reverse(Node node){
		//base situation and only one element
		if(  node.next == null){
			return node;
		}
		
		Node secondNode = node.next;
		
		Node remainingReverse = reverse(secondNode);
		
		Node current = remainingReverse;
		
		while(current.next != null){
			current= current.next;
		}
		
		current.next = node;
		
		node.next = null;
		return remainingReverse;		
	}
	
	
	//注意指针操作的时候，当两个指针同时指向同一个对象的时候，任何一个指针修改了该对象里面的内容，另外个也随之改变
	//具体请参考CloneDemo.java;
	public Node reverse1(Node node){
		
		if(node == null || node.next == null){
			return node;
		}
		
		Node next = node.next;
		Node last = next.next;
		
		Node previous = node;
		
		while(last.next != null){
			
			next.next = previous;
			
			previous = next;
			next = last;
			last = last.next;
			
		}
		
		last.next = next;// reverse last node to last second node
		next.next = previous; // reverse last second to last third node
		//next.next.data = 7;
		node.next = null;// first node point to null;
		
		return last;
	}
	
	
	public Node Nth2LastElement(Node node, int N, Counter count){
		if(node == null){
			return node;
		}
		
		Node tempNode = Nth2LastElement(node.next, N, count);
		count.value++;
		if(count.value == N){
			return node;
		}
		return tempNode;
	}
	
	public Node findLastNElement(Node node, int N){
		//base situation and only one element
				int counter = 0;
				if(  node.next == null){
					return node;
				}
				
				
				Node secondNode = node.next;
				
				Node remainingReverse = findLastNElement(secondNode, N);
				
				Node current = remainingReverse;
				
				while(current.next != null){
					current= current.next;
					counter++;
				}
				
				current.next = node;
				
				//counter++;
				
				if(counter >= N){
					current.next = null;
					Node result = remainingReverse;
					return result;
					
				}
				node.next = null;
				return remainingReverse;	
	}
	/**
	Given a linked list, swap every two adjacent nodes and return its head.<br>

	For example,
	Given 1->2->3->4, you should return the list as 2->1->4->3.<br>

	Your algorithm should use only constant space. You may not modify 
	the values in the list, only nodes itself can be changed.
	
	@param node   The first node the linkedlist head points
	*/
	public Node swapPairs(Node node){
		if(node == null ){
			return null;
		}
		if(size % 2 != 0){
			return node;
		}
		
		Node current = node;
		Node previous = node;
		Node next = current.next;
		Node nextNext = next.next;
		
		node = next;
		while(current.next!=null && next.next !=null){
	        next.next = current;
	        current.next = nextNext;
	        current = current.next;
	        next = current.next;
	        nextNext = next.next;
	        previous.next = next;
	        previous = current;
			
		}
		
		next.next = current;
		current.next = null;
		
		return node;
		
		
	}
	
	public void deleteDup(Node node){
		if(node == null){
			return;
		}
		HashSet<Integer> hs = new HashSet<Integer>();
		Node previous = node;
		while(node != null){
			if(hs.contains(node.data)){
				previous.next = node.next;
				size--;
			}
			else{
				hs.add(node.data);
				previous = node;
			}
			
			node = node.next;
			
		}
		
		
	}
	
	public Node delMiddleNode(Node node){
		if(node == null || node.next == null){
			return node;
		}
		Node next = node.next;
		node.data = node.next.data;
		node.next = next.next;
		return node;
	}
	
	public Node partition(Node node, int num){
		if(node == null || node.next == null){
			return node;
		}
		
		LinkList before = new LinkList();
		LinkList after = new LinkList();
		
		while(node != null){
			if(node.data < num ){
				before.add(node.data);
			}
			else if(node.data >= num ){
				after.add(node.data);
			}
			
			
			node = node.next;
		}
		
		before.tail.next = after.head;
		
		return before.head;
		
	}
	
	public Node partition2(Node node, int num){
		if(node == null || node.next == null){
			return node;
		}
		
		Node beforeStart = null;
		Node beforeEnd = null;
		Node afterStart = null;
		Node afterEnd = null;
		
		while(node != null){
			Node next = node.next;
			node.next = null;
			if(node.data < num ){
				if(beforeStart == null){
					beforeStart = node;
					beforeEnd = beforeStart;
				}
				else{
					beforeEnd.next = node;
					beforeEnd = beforeEnd.next;
				}
			}
			else if(node.data >= num ){
				if(afterStart == null){
					afterStart = node;
					afterEnd = afterStart;
				}
				else{
					afterEnd.next = node;
					afterEnd = afterEnd.next;
				}
			}
			
			
			node = next;
		}
		
		if(beforeStart == null){
			return afterStart;
		}
		
		beforeEnd.next = afterStart;
		return beforeStart;
		
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LinkList list = new LinkList();
		List<Integer> l = new LinkedList<Integer>();
		
		
		
		list.add(3);
		list.add(4);
		list.add(5);
		list.add(6);
		list.add(7);
		list.add(12);
		list.add(11);
		list.add(8);
		list.add(9);
		
		list.deleteDup(list.head);
		System.out.println(list.toString()+ "size is " + list.size );
		list.head = list.partition2(list.head, 10);
		System.out.println(list.toString());
		list.head = list.swapPairs(list.head);
		System.out.println(list.toString());
		//list.head = list.findLastNElement(list.head, 2);
		list.head = list.Nth2LastElement(list.head, 3, list.new Counter());
		System.out.println(list.toString());
		
		list.head = list.reverse1(list.head);
	    System.out.println(list.toString());
	    System.out.println(list.getSize());
	    list.remove(list.head, 4);
	    System.out.println(list.toString());
	    System.out.println(list.getSize());
	    
	    
	}

}
